package fun.coding.leetcode;

public class RegularExpressionMatching {

	public static void main(String[] args) {
		
		RegularExpressionMatching rem = new RegularExpressionMatching();
		System.out.println(rem.isMatch("aa", "a"));
		System.out.println(rem.isMatch("aab", "a*b*c*"));
		System.out.println(rem.isMatch("abbccd", "abc*bc*d"));
		System.out.println(rem.isMatch("", "a*"));
		System.out.println(rem.isMatch("", ""));
		System.out.println(rem.isMatch("a", ""));
		System.out.println(rem.isMatch("aa", "aa"));
		System.out.println("done...");
		
	}
	
	// Thomas's solution, very clean...
	/*
	public boolean isMatch(String s, String p) {
        assert(p!=null && (p.length()==0 || p.charAt(0)!='*'));
        
        if(p.length()==0) return s.length()==0;
        
        if(p.length()==1 || p.charAt(1)!='*'){
            if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0))) 
                return false;
            return isMatch(s.substring(1),p.substring(1));
        }else{
            int i=-1;
            while(i<s.length() && (i<0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
                if(isMatch(s.substring(i+1),p.substring(2))) 
                    return true;
                i++;
            }
            return false;
        }
    }
	*/
	
	public boolean isMatch(String s, String p) {
		if (s == null || p == null) return false;
		
		return isMatchHelper(s, 0, p, 0);
	}
	
	// http://leetcodenotes.wordpress.com/2013/08/25/leetcode-regular-expression-matching/
	private boolean isMatchHelper(String s, int i, String p, int j) {
	    if (j == p.length()) {
	        return i == s.length();
	    }
	    
	    // j+1 is not *
	    if (j == p.length() - 1 || p.charAt(j + 1) != '*') {
	        if (isCharMatch(s, i, p, j)) {
	            return isMatchHelper(s, i + 1, p, j + 1);
	        } else {
	            return false;
	        }
	    } else { // j+1 is *, and j+1 must be less than length
	    	// matching the times with 0 occurrence of a*. 
	    	boolean skip = isMatchHelper(s, i, p, j + 2);
	    	if (skip) return true;
	    	// keep matching. 
	        while (isCharMatch(s, i, p, j)) {
	            if (isMatchHelper(s, i + 1, p, j + 2)) {
	                return true;
	            }
	            i++;
	        }
	    }
		return false;
	}
	
	// compare if char is the same or it is a '.'
	private boolean isCharMatch(String s, int i, String p, int j) {
	    if (i >= s.length() || j >= p.length()) {
	        return false;
	    }
	    return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
	}

}
